package linear_list.leetcode.easy;

/**
 * @Description: 合并两个有序链表
 * 题目链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * @Author Stark
 * @Date 2022/4/6 17:01
 **/
public class Num21_MergeTwoLists {
    int choice = 1;
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(choice == 1){
            //方法一：非递归法
            //使用虚拟头节点
            ListNode dummyHead = new ListNode(0);
            ListNode cur = dummyHead;
            while(list1 != null && list2 != null){
                if(list1.val <= list2.val){
                    cur.next = list1;
                    list1 = list1.next;
                }else{
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            //如果list1走到空，说明list2还没走到空，将list1指向list2
            //否则将直接连接list1
            if(list1 == null)
                list1 = list2;
            cur.next = list1;
            return dummyHead.next;
        }else if(choice == 2){
            //递归法
            //如果一个链表为空，直接返回另一个
            if(list1 == null)
                return list2;
            if(list2 == null)
                return list1;
            if(list1.val <= list2.val){
                //拼接链表
                list1.next = mergeTwoLists(list1.next, list2);
                //返回结点
                return list1;
            }else{
                list2.next = mergeTwoLists(list1,list2.next);
                return list2;
            }
        }
        return null;
    }
}
